package com.wx.datastructure.queue.loop;

import com.wx.datastructure.queue.Queue;

/**
 * @author wx
 * @Description: 线性数据结构-循环数组实现队列
 * @date 2018/12/12 001218:07
 */
public class LoopQueue<E> implements Queue<E> {
    /**
     * 原生java数组
     */
    private E[] data;
    /**
     * front 出队下标
     * tail  入队下标
     */
    private int front, tail;
    /**
     * 元素长度
     */
    private int size;


    public LoopQueue() {
        this(10);
    }


    public LoopQueue(int capacity) {
        //使用循环数组将会浪费一个空间，所以需要额外+1
        this.data = (E[]) new Object[capacity + 1];
        this.front = 0;
        this.tail = 0;
        this.size = 0;
    }

    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.data == null || this.front == this.tail;
    }

    @Override
    public void enqueue(E o) {
        /**
         * 1. %数组长度就是为了循环数组，假设数组总长度是10 this.tail也累加到了10 就相当于回到了索引0最开始的位置
         * 2. 判断入队下标的下个位置 是否等于出队队列的下标，如果相等说明容器满载
         * 3.每次入队，下标都会进行+1 取余数组长度
         */
        if ((this.tail + 1) % this.data.length == this.front) {
            //进行扩容
            resize(getCapacity() * 2);
        }
        this.data[this.tail] = o;
        this.tail = (this.tail + 1) % data.length;
        this.size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        E ret = this.data[this.front];
        this.data[this.front] = null;
        //计算出队的下标 出队下标+1 余数组长度
        front = (front + 1) % this.data.length;
        size--;
        //进行缩容
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("队列为空");
        }
        return this.data[this.front];
    }


    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * @param newCapacity
     * @description: 扩容方法
     * @author: wx
     * @date: 2018/12/12 0012
     * @return: void
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        this.data = newData;
        this.front = 0;
        this.tail = this.size;
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}
